﻿#define _CRT_SECURE_NO_WARNINGS 1
//洛谷p1162（利用bfs做法）
//搜索到n + 1是为了绕过墙，不然的话矩阵被1隔断从（0, 0）开始搜就搜不到下面的未被墙包起来的区域，
//#include<iostream>
//using namespace std;
//typedef pair<int, int>PII;
//const int N = 40;
//int a[N][N],b[N][N];
//int n;
//PII q[N * N];
//void bfs()
//{
//	int hh = 0, tt = 0;
//	q[0] = { 0,0 }; a[0][0] = 1;
//	int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,1,-1 };
//	while (hh <= tt)
//	{
//		PII t = q[hh++];
//		for (int i = 0; i < 4; i++)
//		{
//			int x = t.first + dx[i],  y = t.second + dy[i];
//			if (x >= 0 && x <= n+1 && y >= 0 && y <= n+1 && a[x][y] != 1)
//			{
//				a[x][y] = 1;
//				q[++tt] = { x,y };
//			}
//		}
//	}
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= n; j++)
//			cin >> a[i][j];
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= n; j++)
//			b[i][j] = a[i][j];
//	bfs();
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= n; j++)
//			if (a[i][j] != 1)
//				b[i][j] = 2;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= n; j++)
//		{
//			printf("%d ", b[i][j]);
//		}
//		printf("\n");
//	}
//	return 0;
//}

//题目：850. Dijkstra求最短路 II（堆优化版本）
//给定一个 n个点 m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
//请你求出 1号点到 n号点的最短距离，如果无法从 1号点走到 n号点，则输出 −1。
//输入格式
//第一行包含整数 n和 m。
//接下来 m行每行包含三个整数 x, y, z，表示存在一条从点 x到点 y的有向边，边长为 z。
//输出格式
//输出一个整数，表示 1号点到 n号点的最短距离。
//如果路径不存在，则输出 −1。
//数据范围
//1≤n, m≤1.5×105,图中涉及边长均不小于 0，且不超过 10000。
//数据保证：如果最短路存在，则最短路的长度不超过 109。
//输入样例：
//3 3
//1 2 2
//2 3 1
//1 3 4
//输出样例：
//3
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//#include <queue>
//using namespace std;
//typedef pair<int, int> PII;
//const int N = 1e6 + 10;
//int n, m;
//int h[N], w[N], e[N], ne[N], idx;
//int dist[N];
//bool st[N];
//void add(int a, int b, int c)//如何处理重边和自环呢
//                            //实际上并不需要刻意去处理，因为已经排好序了
//                            //距离更近一定会优先排，然后st就被打上标记，会被continue掉
//{
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//int dijkstra()
//{
//    memset(dist, 0x3f, sizeof dist);
//    dist[1] = 0;
//    priority_queue<PII, vector<PII>, greater<PII>> heap;// 数据类型， 容器， 排序方式
//                                                        //greater 是小根堆排序
//    heap.push({ 0, 1 });// 放入距离， 节点编号
//
//    while (heap.size()) //什么时候结束循环？
//                        //从循环条件来看是当heap里面元素为空时结束循环
//                        //那么什么时候heap为空呢？
//                        //当所有点都已经访问完了，并且离原点更近的点一定会更优先进入循环
//                        //因为小根堆排序， 离原点近的放在前面就算不是与原点直接相连的点
//                        //也会优先放进来
//    {
//        auto t = heap.top();//取出堆里面最小距离的点，然后释放掉
//        heap.pop();
//
//        int ver = t.second, distance = t.first;// ver节点编号
//
//        if (st[ver]) continue; //这时候已经取到了距离最近的点，如果已经
//                                //访问过就结束此次循环，未访问过打上标记
//                                //他是如何判断该点一定是他的距离最优点呢？
//                                //转【1】
//        st[ver] = true;
//
//        for (int i = h[ver]; i != -1; i = ne[i])
//        {
//            int j = e[i];//j是节点编号
//            if (dist[j] > dist[ver] + w[i])//【1】通过for循环遍历其指向的点
//                                            //当存在从起始点到j点更短的路径就进行更新
//                                            //为什么说他一定是最优距离呢？
//                                            //假设有其他点到ver的距离+其到原点的距离小于
//                                            //现有的距离，那么他一定会优先考虑，也就不会
//                                            //有该操作
//            {
//                dist[j] = dist[ver] + w[i];
//                heap.push({ dist[j], j });// 为什么要将其放入堆中？
//                                        //应为存在从起始点到j点更短的路径
//                                        //同时也会对节点距离进行排序
//                                        //短距离放在前面
//            }
//        }
//    }
//    if (dist[n] == 0x3f3f3f3f) return -1;
//    return dist[n];
//}
//int main()
//{
//    scanf("%d%d", &n, &m);
//    memset(h, -1, sizeof h);
//    while (m--)
//    {
//        int a, b, c;
//        scanf("%d%d%d", &a, &b, &c);
//        add(a, b, c);
//    }
//    cout << dijkstra() << endl;
//    return 0;
//}
//

